package com.sfx.算法专题.链表.反转链表;

import com.sfx.算法专题.链表.双指针.Code_3_rotateRight;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: sfx
 * Date: 2023-08-03
 * Time: 12:13
 */
public class Code_2_reverseBetween {
    static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }

    /**
     * 穿针引线法-->一次遍历
     * curr：指向待反转区域的第一个节点 left；
     * next：永远指向 curr 的下一个节点，循环过程中，curr 变化以后 next 会变化；
     * prev：永远指向待反转区域的第一个节点 left 的前一个节点，在循环过程中不变。
     * 每次都是将next放到prev的后面,然后迭代遍历
     * 在需要反转的区间里，每遍历到一个节点，让这个新节点来到反转部分的起始位置。下面的图展示了整个流程。
     */
    static class Solution {
        public ListNode reverseBetween(ListNode head, int left, int right) {
            ListNode dummy = new ListNode(-1);
            dummy.next = head;
            ListNode cur = head;
            ListNode prev = dummy;
            for(int i =1;i<left;++i) {
                cur = cur.next;
                prev = prev.next;
            }
            for(int i =0;i<right-left;++i){
                ListNode next = cur.next;
                cur.next = next.next;
                next.next = prev.next;
                prev.next = next;
            }
            return dummy.next;
        }
    }

    static class Solution2 {
        public ListNode reverseBetween(ListNode head, int left, int right) {
            ListNode dummy = new ListNode(-1);
            dummy.next = head;
            //两次遍历
            ListNode prev = dummy;
            //1.找到待反转节点的前一个节点
            for(int i =0;i<left-1;++i) {
                prev = prev.next;
            }
            //2.找到反转部分部分链表结尾的后一个结点
            ListNode reverseNext = dummy;
            for(int i = 0;i<right;++i) {
                reverseNext = reverseNext.next;
            }
            //3.分别断开,然后使用反转链表,反转中间部分
            ListNode reverseHead = prev.next;
            ListNode reverseTail = reverseNext.next;
            reverseNext.next = null;
            //4.然后将前半部分和后半部分进行连接
            reverseHead = reverseList(reverseHead);
            prev.next = reverseHead;
            while(reverseHead.next !=null) {
                reverseHead= reverseHead.next;
            }
            reverseHead.next = reverseTail;
            return dummy.next;
        }
        private ListNode reverseList(ListNode head) {
            if(head == null || head.next ==null) return head;
            ListNode cur = head;
            ListNode prev = null;
            while(cur != null) {
                ListNode curNext = cur.next;
                cur.next = prev;
                prev = cur;
                cur = curNext;
            }
            return prev;
        }
    }

    static class Solution4 {
        public ListNode reverseBetween(ListNode head, int left, int right) {
            ListNode dummy = new ListNode(-1);
            dummy.next = head;
            //两次遍历
            ListNode prev = dummy;
            //1.找到待反转节点的前一个节点
            for(int i =0;i<left-1;++i) {
                prev = prev.next;
            }

            //2.找到反转部分部分链表结尾的后一个结点
            ListNode reverseNext = dummy;
            for(int i = 0;i<right;++i) {
                reverseNext = reverseNext.next;
            }

            //3.分别断开,然后使用反转链表,反转中间部分
            ListNode reverseHead = prev.next;
            ListNode reverseTail = reverseNext.next;
            prev.next = null;
            reverseNext.next = null;
            reverseList(reverseHead);

            //4.然后将前半部分和后半部分进行连接
            prev.next = reverseNext;//原来的结尾变为反转的开头
            reverseHead.next = reverseTail;//原来的开头变成现在的结尾

            return dummy.next;
        }
        private ListNode reverseList(ListNode head) {
            if(head == null || head.next ==null) return head;
            ListNode cur = head;
            ListNode prev = null;
            while(cur != null) {
                ListNode curNext = cur.next;
                cur.next = prev;
                prev = cur;
                cur = curNext;
            }
            return prev;
        }
    }

    class Solution3 {
        public ListNode reverseBetween(ListNode head, int left, int right) {
            // 因为头节点有可能发生变化，使用虚拟头节点可以避免复杂的分类讨论
            ListNode dummyNode = new ListNode(-1);
            dummyNode.next = head;

            ListNode pre = dummyNode;
            // 第 1 步：从虚拟头节点走 left - 1 步，来到 left 节点的前一个节点
            // 建议写在 for 循环里，语义清晰
            for (int i = 0; i < left - 1; i++) {
                pre = pre.next;
            }

            // 第 2 步：从 pre 再走 right - left + 1 步，来到 right 节点
            ListNode rightNode = pre;
            for (int i = 0; i < right - left + 1; i++) {
                rightNode = rightNode.next;
            }

            // 第 3 步：切断出一个子链表（截取链表）
            ListNode leftNode = pre.next;
            ListNode curr = rightNode.next;

            // 注意：切断链接
            pre.next = null;
            rightNode.next = null;

            // 第 4 步：同第 206 题，反转链表的子区间
            reverseLinkedList(leftNode);

            // 第 5 步：接回到原来的链表中
            pre.next = rightNode;
            leftNode.next = curr;

            return dummyNode.next;
        }

        private void reverseLinkedList(ListNode head) {
            // 也可以使用递归反转一个链表
            ListNode pre = null;
            ListNode cur = head;

            while (cur != null) {
                ListNode next = cur.next;
                cur.next = pre;
                pre = cur;
                cur = next;
            }
        }
    }

    private static ListNode createList() {
        ListNode head1 = new ListNode(1);
        ListNode node1 = new ListNode(2);
        ListNode node2 = new ListNode(3);
        ListNode node3 = new ListNode(4);
        ListNode node4 = new ListNode(5);
        head1.next = node1;
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        return head1;
    }

    public static void main(String[] args) {
        Solution2 solution2 = new Solution2();
        ListNode head = createList();
        solution2.reverseBetween(head,2,4);
    }
}